There are four operations that usually need to be performed on a priority queue.
Finding the first element in the queue PA0 Inserting an element into the queue PA0 Deleting an element from the queue PA0 Changing an element in the queue
The quality of an algorithm and that of its implementation, is measurable based on the efficiency with which these operations can be performed. The efficiency is in terms of the number of memory read/write operations, and the number of compare operations necessary. As an example, consider a priority queue implemented as a linked list of elements arranged in increasing order of priority. Insertion of an element requires traversing the linked list until the position of the element in the linked list is found, and then inserting the element in the list. Similarly deleting an element and changing an element also require traversing the list until the element is located. In the worst case, the entire list of elements would need to be traversed.
In addition to the efficiency of the above operations an algorithm may be measured based on the amount of space it consumes beyond that to hold the elements of the queue.
The present invention is an algorithm to implement a priority queue that requires very little storage beyond that which is required to hold the elements in the queue. With this algorithm and parallel hardware it is possible to insert elements into the queue with no memory reads and a constant number of memory writes, in the worst case.
The priority queueing problem (or more generally, the sorting problem) is defined as the problem of ordering a list of objects according to some linear order. For example, integers may be ordered in increasing or decreasing order of their numerical value.